"""
给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reordered-power-of-2
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

def is_power(N):
    if N <= 0:
        return False
    check = 0
    while(N > 1):
        if N==2:
            break
        N /= 2
        check = N%2
    return check == 0


# 全排列
def dfs(nums, depth, path, used, res):
    # 已经到了叶子节点
    if(depth == len(nums)):
        res.append(path.copy())
        return
    for i in range(len(nums)):
        if used[i] or (i > 0 and used[i - 1] == False and nums[i] == nums[i - 1]):
            continue
        # 还没被选过
        path.append(nums[i])
        used[i] = True
        dfs(nums, depth + 1, path, used, res)
        # 回溯
        path.pop()
        used[i] = False

def permuteUnique(nums):
    path = []
    used = []
    depth = 0
    res = []
    for _ in range(len(nums)):
        used.append(False)
    if len(nums) == 0:
        return res
    nums.sort()
    dfs(nums, depth, path, used, res)
    return res

def cover2_int(nums):
    nums.reverse()
    n = 0
    res = 0
    for i in nums:
        res += i * pow(10, n)
        n += 1
    return res

def cover2_list(n):
    res = []
    while n:
        res.append(n%10)
        n //= 10
    res.reverse()
    return res

class Solution:
    def reorderedPowerOf2(self, n):
        can_get = False
        nums = cover2_list(n)
        res = permuteUnique(nums)
        for item in res:
            if item[0] == 0:
                continue
            if is_power(cover2_int(item)):
                return True
        return can_get

# print(Solution.reorderedPowerOf2(self=None, n = 24))
